package Dynamic_Programming;
/*
* 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
*
* 确定dp数组（dp table）以及下标的含义
    dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。
确定递推公式
    dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
    j * (i - j) 是单纯的把整数拆分为两个数相乘，而j * dp[i - j]是拆分成两个以及两个以上的个数相乘。
    那么在取最大值的时候，为什么还要比较dp[i]呢？
    因为在递推公式推导的过程中，每次计算dp[i]，取最大的而已。
dp的初始化
dp数组如何初始化
    dp[0] dp[1] 无意义
    * dp[2]=1
    * dp[3]=3
确定遍历顺序
举例推导dp数组
* */
public class lc343 {
    public int integerBreak(int n) {
        int[] dp=new int[59];
        dp[2]=1;
        dp[3]=2;
        for (int i = 1; i <n+1 ; i++) {
            for (int j = 0; j <i ; j++) {
                dp[i]=Math.max(dp[i], Math.max((i - j) * j, dp[i - j] * j));
            }
        }
        return dp[n];
    }
}
